As speed requirements of computer processing units have increased, systems employing greater numbers of parallel memory modules have been developed. One such system has in the order of 64 parallel memories, see U.S. Pat. No. 3,537,074, issued Oct. 27, 1970 to R. A. Stokes et al, and assigned to the assignee of the present invention.
Parallel memory systems generally suffer however from unavoidable memory conflicts. Severe storage problems frequently arise in performing matrix computations. Consider for example, a typical two-dimensional matrix having its elements stored column-by-column in a parallel memory array. Under such a storage system, row, forward diagonal and reverse diagonal elements may be accessed in parallel. However, column elements must be accessed serially out of each memory. Thus a memory conflict arises which limits the processing capability of the parallel memory systems.
Other storage systems permit parallel access to a matrix column but may cause a conflict for row, diagonal or other matrix vector access. The conflict problem has been studied, see Budnik and Kuck, "The Organization and Use of Parallel Memories", IEEE TRANSACTIONS ON COMPUTERS, December 1971, pages 1566-1569 and "Access and Alignment of Data in an Array Processor". D. H. Lawrie, IEEE TRANSACTIONS ON COMPUTERS, December 1975. However, attempts to solve the conflict problem generally lead to a relatively complex memory storage system and tend to increase the complexity of aligning the plurality of parallel memories with the associated plurality of arithmetic units or processors.
Further, attempts to resolve the conflict problem in the past generally resulted in systems having an odd number (usually prime) of processors and an even number (usually a power of two) of memory modules, see U.S. Pat. No. 4,101,960, issued July 18, 1978, to R. A. Stokes et al and assigned to the assignee of the present invention.
However, a prime number of processors in an array lead to relatively complex hardware problems in providing a connection network to an even number of memory modules. In a parallel array system such as disclosed in U.S. patent application Ser. No. 097,191 filed Nov. 26, 1979 by G. H. Barnes and assigned to the assignee of the present invention, an Omega type connection network is proposed and a processor array is utilized in which each processor functions with a degree of independence and is not locked-step with all all other processors in the array. In such a system a perfect conflict free storage system cannot be fully utilized due to the imperfections of the Omega type connection network (as compared to a crossbar network, for example) and the non-locked-step functioning of the processor array. All that is required is that the minor conflicts introduced by a slightly imperfect storage system do not contribute significantly to the other imperfections already built into the system. Thus a tradeoff of complete conflict protection for hardware simplicity and other benefits is of great value in an array system, particularly one utilizing other than a crossbar connection network and a non-locked-step processor array. This tradeoff is especially beneficial in a system such as disclosed in the above cited U.S. Ser. No. 097,191 patent application wherein each processor in an array thereof must have sufficient hardware and capability to generate its storage mapping procedures.